package com.datastructure.test.removeduplicateletters;

import java.util.*;

public class RemoveDuplicateLetters {

    public static void main(String[] args) {
        RemoveDuplicateLetters removeDuplicateLetters = new RemoveDuplicateLetters();
        String duplicateLetters = removeDuplicateLetters.removeDuplicateLetters("abcd");
        System.out.println(duplicateLetters);
    }

    public String removeDuplicateLetters(String str) {
        int[] last=new int[128];//a~z的ASCII码为97~122,last用来记录字母最后出现的坐标
        for(int i=0;i<str.length();i++){
            last[str.charAt(i)]=i;
        }
        Set<Integer> visited=new HashSet<>();
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<str.length();i++){
            int c=str.charAt(i);
            if(visited.contains(c))continue;
            visited.add(c);
            //如果栈顶字母比当前字母大，那就要同时考虑栈顶字母是否是最后出现的位置
            //如果不是最后出现的位置则可以弹出栈顶，反正后面还有。
            while(!stack.isEmpty()&&stack.peek()>c&&i<last[stack.peek()]){
                visited.remove(stack.pop());
                //visited是用来记录当前字母是否被使用过，删掉栈顶的大字母，后面符合条件的字母会再被记录
                //如果符合最终条件的字母已被记录，那么就会被11行代码所跳过。
            }
            stack.push(c);
        }
        StringBuilder sb=new StringBuilder();
        for(int i:stack)sb.append((char)i);
        return sb.toString();
    }

//    public String removeDuplicateLetters (String str) {
//        // write code here
//        Map<Character,Integer> map = new LinkedHashMap<>();
//        char[] charArray = str.toCharArray();
//        for (int i = 0; i < charArray.length; i++) {
//            if(map.containsKey(charArray[i])){
//                int lastIndex = map.get(charArray[i]);
//                String str1 = str.substring(0,lastIndex)+str.substring(lastIndex+1);
//                String str2 = str.substring(0,i)+str.substring(i+1);
//                if(str1.compareTo(str2)<0){
//                    return removeDuplicateLetters(str1);
//                } else {
//                    return removeDuplicateLetters(str2);
//                }
//            }
//            map.put(charArray[i],i);
//        }
//        return str;
//    }
}
